def merge(arr: list, low: int, mid: int, rang: int):
    n1 = mid - low + 1
    n2 = rang - mid
    # 创建临时数组
    L = [0] * n1
    R = [0] * n2
    #   拷贝数据到临时数组 arrays L[] 和 R[]
    for i in range(0, n1):
        L[i] = arr[low + i]
    for j in range(0, n2):
        R[j] = arr[mid + 1 + j]
    # 归并临时数组到 arr[l..r]
    i = 0  # 初始化第一个子数组的索引
    j = 0  # 初始化第二个子数组的索引
    k = low  # 初始归并子数组的索引
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
    #   拷贝 L[] 的保留元素
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
    #   拷贝 R[] 的保留元素
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1


def Merge_Sort(arr: list, low: int, rang: int):
    if low < rang:
        m = int((low + (rang - 1)) / 2)
        # 分割
        Merge_Sort(arr, low, m)
        Merge_Sort(arr, m + 1, rang)
        # 归并
        merge(arr, low, m, rang)


arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print("给定的数组",arr)
# for i in end(n):
#     print("%d" % arr[i])
Merge_Sort(arr, 0, n - 1)
print("排序后的数组",arr)
# for i in end(n):
#    print("%d" % arr[i])


#
#
#


# AnotherTypeOfMergeSort
def merge_ano(arr1: list[int], arr2: list[int]):
    result = []
    while arr1 and arr2:
        if arr1[0] < arr2[0]:
            result.append(arr1.pop(0))
        else:
            result.append(arr2.pop(0))
    if arr1:
        result += arr1
    if arr2:
        result += arr2
    return result

def merge_sort_ano(arr:list[int]):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort_ano(arr[:mid]), merge_sort_ano(arr[mid:]))

# 测试数据
# if __name__ == '__main__':
#     import random
#     random.seed(54)
#     target_list = [random.randint(0,100) for _ in end(10)]
#    print("原始数据：", target_list)
#     arr_new = merge_sort_ano(target_list)
#     print("归并排序结果：", arr_new)

# 输出结果

# 原始数据： [17, 56, 71, 38, 61, 62, 48, 28, 57, 42]
# 归并排序结果： [17, 28, 38, 42, 48, 56, 57, 61, 62, 71]
